package code401_500.code1_10;

import java.util.ArrayList;
import java.util.List;

/**
 * 二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
 *
 * 例如，下面的二进制手表读取 "3:25" 。
 *
 * 给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
 *
 * 小时不会以零开头：
 *
 * 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
 * 分钟必须由两位数组成，可能会以零开头：
 *
 * 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。
 *
 * 输入：turnedOn = 1
 * 输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
 *
 * 输入：turnedOn = 9
 * 输出：[]
 */
public class _401binaryWatch {

    /**
     * 考虑可能性后的全排列问题
     * 我们可以枚举小时的所有可能值 [0,11][0,11]，以及分钟的所有可能值 [0,59][0,59]，并计算二者的二进制中 11 的个数之和，
     * 若为turnedOn，则将其加入到答案中。
     * 执行用时：     * 10 ms     * , 在所有 Java 提交中击败了     * 62.71%     * 的用户
     * 内存消耗：     * 37 MB     * , 在所有 Java 提交中击败了     * 77.81%     * 的用户
     * @param turnedOn
     * @return
     */
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                    ans.add(i + ":" + (j < 10 ? "0" : "") + j);
                }
            }
        }
        return ans;
    }

    /**
     * 枚举2^10次方的所有灯的开关组合，高四位为小时，第六位为分钟。若小时和分钟均在合法范围内，且二进制中1的个数为turnedOn，则将其加入到答案中。
     * 执行用时：     * 10 ms     * , 在所有 Java 提交中击败了     * 62.71%     * 的用户
     * 内存消耗：     * 38.5 MB     * , 在所有 Java 提交中击败了     * 44.15%     * 的用户
     * @param turnedOn
     * @return
     */
    public List<String> readBinaryWatch1(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int i = 0; i < 1024; ++i) {
            int h = i >> 6, m = i & 63; // 用位运算取出高 4 位和低 6 位
            if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
                ans.add(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
        return ans;
    }
}
